# 力扣1514. 概率最大的路径（来源：力扣）
# 给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，图由边的列表表示。
# edges[i] = [a, b, w] 表示连接节点 a 和 b 的一条无向边，成功概率为 w。
# 从起点 start 到终点 end 找到成功概率最大的路径，并返回其成功概率。如果不存在从 start 到 end 的路径，返回 0。
List = list
def solve(n: int, edges: List[List[int]], start: int, end: int) -> float:
    # 定义邻接表
    graph = {}
    prob = {}
    for edge in edges:
        graph[edge[0]] = edge[1:]
    
    for node in range(n):
        prob[node] = 0
    import heapq
    heap = [start]

    while heap:
        curr = heapq.heappop(heap)
        if prob[curr] < graph[curr][1]: continue
        if curr == end: break
        for next,p in graph[curr]:
            if prob[curr] * p > prob[next]:
                prob[next] = prob[curr] * p 
                heapq.heappush(heap,next)
    return prob[end]
if __name__ == "__main__":
    s = solve(3,[[0, 1, 0.5], [1, 2, 0.5], [0, 2, 0.3]],0,2)
    print(s)